//
// Created by DengLibin on 2019/1/11 0011.
//
#include <iostream>
using namespace std;
 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

 /**
  * 反转链表 循环实现
  * @param headNode
  * @return
  */
 ListNode * reverseListNode(ListNode * headNode){
     if(headNode == NULL){
         return NULL;
     }
     //定义三个中间变量 当作滑动窗口
     ListNode * temp1 = NULL;
     ListNode * temp2 = headNode;
     ListNode * temp3 = temp2->next;
     while (true){
         temp2->next = temp1;
         temp1 = temp2;
         temp2 = temp3;
         if(temp2 == NULL){ //跳出循环
             break;
         }
         temp3 = temp3->next;
     }
       return temp1;
 }

 /**
  * 反转链表 递归实现
  * @param preNode
  * @param headNode
  * @return
  */
 ListNode * reverseListNode2(ListNode* preNode,ListNode * headNode){
     ListNode * next = headNode->next;
     headNode->next = preNode;
     if(next != NULL){
         return reverseListNode2(headNode,next);
     }
     return headNode;
 }

ListNode* reverseKGroup(ListNode* head, int k) {
     if(head == NULL){
         return NULL;
     }
     ListNode * tempNode = head;//指针(游标)
     ListNode * tempHead = head; //每一段的头节点
     ListNode * tempTail = NULL; //每一段的尾节点
     ListNode * resHead = NULL; //用于返回的头节点
     int i = 0;
     while(tempNode != NULL){
        i++;
        if(i % k == 0){ //满足反转条件
            ListNode * next = tempNode->next; //记录下一个节点
            tempNode->next = NULL; //先置为空用于反转
            ListNode * newHead = reverseListNode(tempHead);//反转
            if(tempTail == NULL){
            } else{
                tempTail->next = newHead; //上一段的尾部指向当前这一段的头部
            }
            tempTail = tempHead; //更新这一段的尾部
            tempTail->next = next; //连接下一个节点

            if(resHead == NULL){
                resHead = newHead; //给返回的节点赋值 执行一次
            }
            tempHead = next; //初始化下一段的头部
            tempNode = tempTail; //游标变为这一段的尾部
        }
        tempNode = tempNode->next;
     }
     if(resHead == NULL){
         resHead = head;
     }
    return resHead;
}

 int main60(){
     ListNode l1(1);
     ListNode l2(2);
     ListNode l3(3);
     ListNode l4(4);
     ListNode l5(5);
     ListNode l6(6);
   //  l1.next = &l2;
     //l2.next = &l3;
     //l3.next = &l4;
     //l4.next = &l5;
     //l5.next = &l6;
     ListNode* head =  reverseKGroup(&l1,1);
     ListNode * temp = head;
     while(temp != NULL){
         cout <<temp->val<<",";
         temp = temp->next;
     }
     return 0;
 }


